19填空对于以下等价类，采用“加权合并规则”（也称“重量权衡合并规则”），进行并查运算，给出最后父结点索引序列。1-25-11-60-37-46-95-30-84–8注意：当合并大小相同的两棵树的时候，将第二棵树的根指向第一棵树的根；根结点的索引是它本身；数字之间用一个空格隔开Giventhefollowingequivalencepairs,pleaseusethe”union-by-weightrule”andtheUNION/FINDalgorithmtoobtainthefinalparentnodeindexsequence.1-25-11-60-37-46-95-30-84-8Notice:Whenwemergetwotreeswiththesamesize,welettherootofthesecondtreepointtotherootofthefirsttree.Theparentindexoftherootnodeisitself.Separatethenumberswithonlyonespace.
20填空根据伪满二叉树的前序序列，求ltag-rlink的二叉树前序遍历比如：给出伪满二叉树的前序序列如下：A’B’DG’/HC’E’FI/则可以求出ltag-rlink的二叉树前序遍历为0A50B31D-11G41H-10C-10E81F-11I-1(注：各个结点按照“ltag结点名rlink”的方式给出，结点之间用一个空格分隔）现给出伪满二叉树的前序序列如下：A’B’C’/IHD’E’G/F则所求出ltag-rlink的二叉树前序遍历为Accordingtothepre-ordertraversalsequenceofa”pseudofullbinarytree”,pleasewritedownthepre-ordertraversalsequenceofthisbinarytreeinan”ltag-rlink”form.Forexample:Giventhepre-ordertraversalsequenceofa”pseudofullbinarytree”likethis:A’B’DG’/HC’E’FI/Thenwecangetthepre-ordertraversalsequenceofthisbinarytreeinthe”ltag-rlink”form:0A50B31D-11G41H-10C-10E81F-11I-1(P.S.Theformofeachnodeshouldbe”LtagNodeRlink”,andallthenodesareseparatedbyasinglespace.)Now,giventhepre-ordertraversalsequenceofa”pseudofullbinarytree”like”A’B’C’/IHD’E’G/F”,pleasewritedownthepre-ordertraversalsequenceofthisbinarytreeinthe”ltag-rlink”form.
21单选若无向图G的顶点度数最小值大于等于x时，G至少有一条回路。求x的最小值。IftheminimumdegreeofverticesofundirectedgraphGisbiggerthanorequaltox,andGhaveatleastonecircuit.Whatistheminimumvalueofx?
A.1
B.2
C.3
D.4
22单选用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m的路径相连，则只要检查_________的第i行第j列的元素是否为零即可。UsinganadjacencymatrixAtorepresentagraph,wejustneedtocheckwhethertheelementintherowi,columnjof________iszerototellwhetherthereisapathwithlengthmconnectingvertexViandVj.
A.
B.mA
C.A
D.
23填空请使用Kruskal算法求出下图的最小生成树，依次写出每次被选择的合法的合并代价最小的边的编号，用一个空格分隔（如果同时存在多条边满足要求，选择编号最小的）。顶点a到顶点b（a<b）之间的边编号为ab，例如图中权值为1的边编号为45。PleaseuseKruskalalgorithmforthefollowinggraphtofindtheminimumspanningtree.Writedowntheedgelabelswhichareselectedintheminimumspanningtreeonebyone(iftherearemultiplevalidedges,selectthevertexwiththeminimumlabel).Thelabelofanedgeconnectingvertexaandvertexbisab(a<b).Forexample,theedgewithaweightof1inthegraphislabeled45.(Separatedifferentlabelswithasingleblankspace.)
数据结构与算法
北京大学
军职在线答案
大学网课